1549D - Integers Have Friends - CodeForces Solution

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;  

// less<int> -> increasing order, greater<int>->decreasing order, less_equal<int> -> work as multiset
// typedef tree< long long int, null_type, less_equal< long long int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#define ordered_set tree<long long, null_type,less_equal<long long>, rb_tree_tag,tree_order_statistics_node_update>
// find_by_order(index) -> iterator of element at x
// order_of_key(key) -> all element strictly less than key.

using namespace std;
#define ll long long
#define ld long double
#define en "\n"
#define pb push_back
#define vec vector<ll>
#define lowb(a, x) (lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) (upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mod 1000000007

#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(0);

template <typename T>
istream &operator>>(istream &in, vector<T> &v)
{
    for (auto &i : v)
        cin >> i;
    return in;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> &v)
{
    for (auto &i : v)
        cout << i << " ";
    return out;
}
ll modInverse(ll A, ll M){ll m0 = M; ll y = 0, x = 1;if (M == 1)return 0;while (A > 1) {    ll q = A / M;ll t = M; M = A % M, A = t; t = y; y = x - q * y;x = t;}if (x < 0)x += m0;return x;}
ll fact(ll num){if(num==0) return 1;return (num)*(fact(num-1))%mod ;}
ll power(long long x, unsigned int y, int p){ int res = 1; x = x % p; if (x == 0) return 0; while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1; x = (x*x) % p;}return res;}
 

void update_segement_tree(ll index , ll val, ll i, ll j, ll node,vector<ll>& seg)
{
    if(i>index || j<index)
    {
        return ;
    }
    if(i==j && j==index)
    {
        seg[node] = val;
        return ;
    }
    ll mid = (i+j)/2;
    update_segement_tree(index, val, i, mid, node*2+1, seg);
    update_segement_tree(index, val, mid+1, j, node*2+2, seg);
    seg[node] = __gcd(seg[node*2+1], seg[node*2+2]);
}
ll get_max_value_bt_i_and_j(ll  ri, ll  rj, ll i, ll j, ll node,vector<ll>& seg)
{
   if(i>rj || j<ri)
   {
     return 0;
   }
    if(i>=ri && j<=rj)
    {
        return seg[node];
    }
    ll mid = (i+j)/2;
    ll a =  get_max_value_bt_i_and_j(ri, rj, i, mid, node*2+1, seg);
    ll b = get_max_value_bt_i_and_j(ri, rj, mid+1, j, node*2+2, seg);
    return  __gcd(a, b);
}

void solve()
{
 ll n;
 cin>>n;
 vec v(n);
 cin>>v;
//  if(n==1)
//  {
//     if(v[0]>1)
//     cout<<1<<en;
//     else
//     cout<<0<<en;
//  }
 vec diff(n-1);
 for(int  i = 1;i<n;i++)
 {
    diff[i-1] = abs(v[i]-v[i-1]);
 }  
 vector<ll>seg(n*4,0);
 for(int i =  0;i<diff.size();i++)
 {
    update_segement_tree(i, diff[i], 0, diff.size()-1,0,seg);
 }
 ll res = 1;


 ll i = 0;
 ll j = 0;
 while(j<n-1 )
 {
    while(j<n-1  &&  get_max_value_bt_i_and_j(i, j, 0, diff.size()-1,0, seg)!=1)
    j++;
    res = max(res, j-i+1);
    if(j<n-1 && i<j && get_max_value_bt_i_and_j(i, j, 0, diff.size()-1,0, seg)==1)
    i++;
    if(i==j && diff[i]==1)
    {
        i++;
        j++;
    }
   
 }
// for(int i = 0;i<diff.size();i++)
// {
//     ll st = i;
//     ll end = diff.size()-1;
//     ll anss = 0;
//     int inc = 0;
//     while(st<=end)
//     {
//         ll mid = (st+end)/2;
//         ll an = get_max_value_bt_i_and_j(i, mid, 0, diff.size()-1,0, seg);
//         if(an>1)
//         {
//             inc = mid;
//             anss = max(anss, mid-i+1+1); 
//             st =mid+1;
//         }
//         else
//         end = mid-1;
//     }
   
    
//     res =max(res, anss);
//     // if(inc>0)
//     // i+= inc-1;
// }
  cout<<res<<en;

}

int main()
{
   fast;
   ll t;
   t =1;
   cin>>t; 
   while(t--)
   {
     solve();
   }
}